package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/distinct-subsequences-ii/description/
 * @create 2025/8/27 14:23
 * @since JDK17
 */

public class Solution10 {
    static int N = ((int) (1e9 + 7));
    public int distinctSubseqII(String str) {
        char[] s = str.toCharArray();
        int[] dp = new int[26];
        int all = 1, newAdd;
        for (char c : s) {
            newAdd = (all - dp[c - 'a'] + N) % N;
            dp[c - 'a'] = (dp[c - 'a'] + newAdd) % N;
            all = (all + newAdd) % N;
        }
        return (all - 1 + N) % N;
    }
}
